/**
 * 
 */
package leetCode;

import java.util.Stack;

/**
 * @author zhong
 *
 */
public class ValidateStackSequences {
	public boolean validateStackSequences(int[] pushed, int[] popped) {
		Stack<Integer> stack = new Stack<>();
		int i = 0, j = 0;
		int n = pushed.length;
		while (i < n) {
			while (i < n && pushed[i] != popped[j]) {
				stack.push(pushed[i++]);
			}
			if (i < n) {
				stack.push(pushed[i++]);
			}
			while (!stack.isEmpty() && stack.peek() == popped[j]) {
				stack.pop();
				j++;
			}
		}
		return j == n;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] pushed = { 1, 2, 3, 4, 5 }, popped = { 4, 5, 3, 2, 1 };
		System.out.println(new ValidateStackSequences().validateStackSequences(pushed, popped));
	}

}
